package algorithms.heap;

import algorithms.tree.BinaryNode;
import algorithms.tree.BinaryTree;

/**
 * 左偏树（英语：leftist tree 或 leftist
 * heap），也可称为左偏堆、左倾堆，是计算机科学中的一种树，是一种优先队列实现方式，属于可并堆，在信息学中十分常见
 * ，在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中，左偏树都有着广泛的应用。
 * 斜堆是比左偏树更为一般的数据结构。 左偏堆的合并操作的平摊时间复杂度为O(log
 * n)，而完全二叉堆为O(n)。左偏堆适合基于合并操作的情形。
 * 由于左偏堆已经不是完全二叉树，因此不能用数组存储表示，需要用链接结构。
 * 
 * 
 * 定义:
 * 
 * 左偏树的节点的距离值
 * 左偏树是一种可并堆的实现。左偏树是一棵二叉树,它的节点除了和二叉树的节点一样具有左右子树指针( left,
 * right ) 外,还有两个属性:
 * 键值和距离（英文文献中称为s-value）。键值用于比较节点的大小。距离的定义如下： 当且仅当节点 i
 * 的左子树且右子树为空时，节点被称作外节点（实际上保存在二叉树中的节点都是内节点，外节点是逻辑上存在而无需保存。
 * 把一颗二叉树补上全部的外节点，则称为extended binary tree）。节点 i 的距离是节点 i
 * 到它的后代中的最近的外节点所经过的边数。特别的,如果节点 i 本身是外节点,则它的距离为
 * 0;而空节点的距离规定为-1
 * 
 * @author shaoyuxia
 *
 *         小根堆
 */
public class LeftistMinHeap extends BinaryTree<Integer> {

	public LeftistMinHeap(Integer key) {
		this.rootNode = new LeftistBinaryNode(key);
	}

	public LeftistMinHeap() {
	}

	/**
	 * 每次pop剔除树当前根节点，然后重新合并左右子树构成新树
	 * 
	 * @return
	 */
	public BinaryNode<Integer> pop() {
		BinaryNode<Integer> node = this.rootNode;
		if (node == null) {
			return null;
		}
		BinaryNode<Integer> left = rootNode.getLeft();
		BinaryNode<Integer> right = rootNode.getRight();
		if (left != null && right != null) {
			this.rootNode = merge0(left, right);
		} else if (right == null && left != null) {
			rootNode = left;
		} else if (right != null && left == null) {
			rootNode = right;
		} else {
			rootNode = null;
		}
		return node;
	}

	public void merge(BinaryNode<Integer> b) {
		if (rootNode == null) {
			rootNode = b;
		} else {
			rootNode = merge0(rootNode, b);
		}
	}

	/**
	 * 函数merge总是在右子树上进行递归调用，因此左偏堆的性质得以保持。
	 * 
	 * 这样 就保证了算法的复杂度为O(lgn)。
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	public BinaryNode<Integer> merge0(BinaryNode<Integer> a, BinaryNode<Integer> b) {
		if (a == null) {
			return b;
		}
		if (b == null) {
			return a;
		}
		// 小根堆，小的key上位，大key子树和小key子树的右子树合并，合并结果作为小key节点的右子树
		if (a.getKey() < b.getKey()) {
			a.setRight(merge0(a.getRight(), b));
			checkRankAndSwip((LeftistBinaryNode) a);
			return a;
		} else {
			b.setRight(merge0(b.getRight(), a));
			checkRankAndSwip((LeftistBinaryNode) b);
			return b;
		}

	}

	/**
	 * 检查左右子树的rank，要保证小rank的子树是右子树，故可能需要交换位置
	 * 
	 * @param a
	 */
	public void checkRankAndSwip(LeftistBinaryNode a) {
		if (a != null) {
			LeftistBinaryNode left = (LeftistBinaryNode) a.getLeft();
			LeftistBinaryNode right = (LeftistBinaryNode) a.getRight();
			if (left == null || (left != null && right != null && left.getRank() < right.getRank())) {
				a.setLeft(right);
				a.setRight(left);
				if (a.getRight() != null) {
					a.setRank(((LeftistBinaryNode) a.getRight()).getRank() + 1);
				}
			} else {
				if (a.getLeft() != null) {
					a.setRank(((LeftistBinaryNode) a.getLeft()).getRank() + 1);
				}
			}
		}
	}

	/**
	 * 左偏树的节点类，基于二叉树的节点增加rank属性
	 * 
	 * @author shaoyuxia
	 *
	 */
	public static class LeftistBinaryNode extends BinaryNode<Integer> {

		/**
		 * 节点到外节点最近的距离值（外节点就是nil节点，叶子节点的子节点，逻辑上的节点，实际上不存在。
		 */
		private int rank = 0;

		public LeftistBinaryNode(Integer key) {
			super(key);
			this.rank = 1;
		}

		/**
		 * @return the rank
		 */
		public int getRank() {
			return rank;
		}

		/**
		 * @param rank
		 *            the rank to set
		 */
		public void setRank(int rank) {
			this.rank = rank;
		}

	}

}
